package dfs;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * MinimumDepthOfBinaryTree
 *
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description: 二叉树的最小深度 https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
 * @date 2021/6/19
 **/
public class MinimumDepthOfBinaryTree {

    /**
     * 使用bfs，按层序进行遍历，最先遇到的叶子节点，到该叶子节点的距离最短
     */
    class Solution1 {
        public int minDepth(TreeNode root) {
            int depth = 0;
            boolean isContinue = true;
            if (root == null) return depth;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty() && isContinue) {
                int size = queue.size();
                for (; size > 0; size--) {
                    TreeNode node = queue.poll();
                    if (node.left == null && node.right == null) {
                        isContinue = false;
                        break;
                    }
                    if (node.left != null) {
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                    }
                }
                depth++;
            }
            return depth;
        }
    }

    /**
     * 使用dfs，使用set来作为visited，保存访问过的节点，叶子节点：left与right都为null，不然不能称之为叶子节点
     */
    class Solution2 {
        int min = Integer.MAX_VALUE;

        public int minDepth(TreeNode root) {
            if (root == null) return 0;
            Set<TreeNode> visited = new HashSet<>();
            int depth = 1;
            dfs(root, visited, depth);
            return min == Integer.MAX_VALUE ? 0 : min;
        }

        private void dfs(TreeNode node, Set<TreeNode> visited, int depth) {
            if (visited.contains(node)) {
                return;
            }
            visited.add(node);
            if (depth >= min) return;
            if (node.left == null && node.right == null) {
                min = Math.min(depth, min);
            }
            if (node.left != null) {
                dfs(node.left, visited, depth + 1);
            }
            if (node.right != null) {
                dfs(node.right, visited, depth + 1);
            }
        }
    }


    /**
     * 使用dfs，与上一种写法不同，二叉树从上到下遍历，天然到避免了重复
     */
    class Solution3 {
        public int minDepth(TreeNode root) {
            if (root == null) return 0;
            int min = findMinDepth(root);
            return min;
        }

        public int findMinDepth(TreeNode root) {
            if (root == null) {
                return Integer.MAX_VALUE;
            }
            if (root.left == null && root.right == null) {
                return 1;
            }
            int leftHeight = findMinDepth(root.left);
            int rightHeight = findMinDepth(root.right);
            return Math.min(leftHeight, rightHeight) + 1;
        }
    }


    /**
     * 使用dfs，在方法二的基础上进行了一些改进，不需要使用visited来去重，二叉树自上而下遍历，天然的就避免了重复
     */
    class Solution4 {
        int min = Integer.MAX_VALUE;

        public int minDepth(TreeNode root) {
            if (root == null) return 0;
            int depth = 1;
            dfs(root, depth);
            return min == Integer.MAX_VALUE ? 0 : min;
        }

        private void dfs(TreeNode node, int depth) {
            if (depth >= min) return;
            if (node.left == null && node.right == null) {
                min = Math.min(depth, min);
            }
            if (node.left != null) {
                dfs(node.left, depth + 1);
            }
            if (node.right != null) {
                dfs(node.right, depth + 1);
            }
        }
    }
}
